#include <stdlib.h>
#include <iostream>

using namespace std;

struct node
{
	int value;
	struct node *left;
	struct node *right;
};

/* Convert a binary search tree into a sorted double-linked list
 * Input: 
 * 	root - the head of tree
 *	head - head node of coverted list
 *	tail - tail node of coverted list
 */
void tree2list(struct node *root, struct node *&head, struct node *&tail)
{
	struct node *lhead, *ltail, *rhead, *rtail;

	//cout<<root->value<<endl;

	//change left tree to list
	if(root->left)
	{
		//cout<<"root:"<<root->value<<"  root->left:"<<root->left->value<<endl;
		tree2list(root->left, lhead, ltail);
		//cout<<"1?"<<endl;
		head = lhead;
		//cout<<"2?"<<endl;
		ltail->right = root;
		//cout<<"3?"<<endl;
		root->left = tail;
		//cout<<"4?"<<endl;
	}
	else
		head = root;
	
	//change right tree to list
	if(root->right)
	{
		tree2list(root->right, rhead, rtail);
		tail = rtail;
		root->right = rhead;
		rhead->left = root;
	}
	else
		tail = root;
	
	//cout<<"OK"<<endl;
	
	head->left = NULL;
	tail->right = NULL;

	return;
}

/*
 * Print double-linked list
 * Input:
 * 	head - head of list
 * 	tail - tail of list
 */
void printList(struct node *head, struct node *tail)
{
	struct node *p = head;
	while(p)
	{
		cout<<p->value;
		p = p->right;
		if(p)
			cout<<"<->";
	}
	cout<<endl;
}

int main()
{
	struct node a10, a6, a14, a4, a8, a12, a16;
	struct node *head, *right;

	a10.left = &a6;
	a10.right = &a14;
	a10.value = 10;
	
	a6.left = &a4;
	a6.right = &a8;
	a6.value = 6;
	
	a14.left = &a12;
	a14.right = &a16;
	a14.value = 14;

	a4.left = NULL;
	a4.right = NULL;
	a4.value = 4;

	a8.left = NULL;
	a8.right = NULL;
	a8.value = 8;

	a12.left = NULL;
	a12.right = NULL;
	a12.value = 12;

	a16.left = NULL;
	a16.right = NULL;
	a16.value = 16;

	cout<<"initail OK!"<<endl;
	tree2list(&a10, head, right);
	printList(head, right);
}
